0% completed
Problem Statement
Given an array nums containing only 1 and 0 digits, return the maximum length of the contiguous subarray having an equal number of 1 and 0.
Examples
- Example 1:
- Input:
[0, 1] - Expected Output:
2 - Justification: The longest subarray with equal numbers of 0s and 1s is [0, 1].
- Input:
- Example 2:
- Input:
[1, 1, 0, 0, 1, 1, 0] - Expected Output:
6 - Justification: The subarray [1, 0, 0, 1, 1, 0] contains three 0s and three 1s.
- Input:
- Example 3:
- Input:
[0, 1, 1, 0, 1, 0, 0, 1, 1] - Expected Output:
8 - Justification: The subarray from the first to the eighth element is the longest with an equal number of 0s and 1s.
- Input:
Solution
To solve this problem, we'll utilize a hash map to keep track of the balance between 0s and 1s at each index. The balance is calculated by treating 0 as -1 and 1 as +1 and adding these values cumulatively. The hash map will store each unique cumulative balance with its earliest index. If we encounter the same balance again, it means the subarray between these two indices has an equal number of 0s and 1s. The reason this approach is effective is that it reduces the problem to a single pass through the array, updating the hash map and checking for the longest balanced subarray as we go.
Step-by-step Algorithm
-
Initialize Variables:
- Create a map/dictionary
balanceMapto keep track of cumulative balances and their first occurrence indexes. - Initialize two variables:
cumulativeBalanceto 0 (to keep track of the balance between 0s and 1s) andmaxLengthto 0 (to store the length of the longest subarray found).
- Create a map/dictionary
-
Iterate Through the Array:
- Loop through each element of the array, using a variable
ifor indexing.
- Loop through each element of the array, using a variable
-
Update Cumulative Balance:
- For each element, update
cumulativeBalance. Decrease by 1 if the element is 0; otherwise, increase by 1.
- For each element, update
-
Check and Update the Map:
- If
cumulativeBalanceis already present inbalanceMap, calculate the length of the current balanced subarray by subtracting the index stored inbalanceMap[cumulativeBalance]from the current indexi. UpdatemaxLengthif this length is greater than the currentmaxLength. - If
cumulativeBalanceis not present inbalanceMap, add it to the map with the value of the current indexi.
- If
-
Return the Result:
- After the loop, return
maxLengthas the result.
- After the loop, return
Algorithm Walkthrough
Using Example 2: [1, 1, 0, 0, 1, 1, 0]
-
Initialization:
balanceMap = {0: -1}cumulativeBalance = 0,maxLength = 0
-
Iterate and Update:
-
Index 0 (Element 1):
- Update
cumulativeBalanceto 1. - Update
balanceMap:{0: -1, 1: 0} maxLength: 0 (no change).
- Update
-
Index 1 (Element 1):
- Update
cumulativeBalanceto 2. - Update
balanceMap:{0: -1, 1: 0, 2: 1} maxLength: 0 (no change).
- Update
-
Index 2 (Element 0):
- Update
cumulativeBalanceto 1 (since it's seen before, check for subarray). balanceMap:{0: -1, 1: 0, 2: 1}maxLength:max(0, 2 - 0) = 2(subarray from index 0 to 2).
- Update
-
Index 3 (Element 0):
- Update
cumulativeBalanceto 0 (seen before, check for subarray). balanceMap:{0: -1, 1: 2, 2: 1}maxLength:max(2, 3 - (-1)) = 4(subarray from index 0 to 3).
- Update
-
Index 4 (Element 1):
- Update
cumulativeBalanceto 1 (seen before, check for subarray). balanceMap:{0: -1, 1: 0, 2: 1}maxLength:max(4, 4 - 0) = 4(no change).
- Update
-
Index 5 (Element 1):
- Update
cumulativeBalanceto 2 (seen before, check for subarray). balanceMap:{0: -1, 1: 0, 2: 1}maxLength:max(4, 5 - 1) = 4(no change).
- Update
-
Index 6 (Element 0):
- Update
cumulativeBalanceto 1 (seen before, check for subarray). balanceMap:{0: -1, 1: 0, 2: 1}maxLength:max(4, 6 - 0) = 6(subarray from index 0 to 6).
- Update
-
-
Result:
- Final
maxLengthis 6, which is the length of the longest contiguous subarray with an equal number of 0s and 1s.
- Final
Code
Complexity Analysis
Time Complexity
The algorithm traverses the array once so time complexity is O(n), where n is the length of the array. Map/dictionary operations like insertion and lookup take O(1) time on average, so the time complexity is linear.
Space Complexity
In the worst case, the map/dictionary might store an entry for every element in the array, leading to a space complexity proportional to the size of the input array, i.e., O(n) .
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity